package leetcode_core.leetcode_6;

import java.util.Random;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2023年02月01日 10:16
 */
public class FindKthLargest {
    public int findKthLargest(int[] nums, int k) {
        shuffle(nums);
        int lo = 0,hi = nums.length-1;
        k = nums.length - k;
        while (lo <= hi){
            int p = partition(nums,lo,hi);
            if(p < k){
                lo = p+1;
            }else if(p > k ){
                hi = hi-1;
            }else{
                return nums[p];
            }
        }
        return -1;
    }

    /**
     * 打乱数组的顺序,避免极端情况
     * @param nums
     */
    private void shuffle(int[] nums){
        Random random = new Random();
        int n = nums.length;
        for(int i = 0;i<n;i++){
            //n-i
            int r = i + random.nextInt(n-i);
            swap(nums,i,r);
        }
    }

    /**
     * 在[lo,hi]中产生一个分界点
     * @param nums
     * @param lo
     * @param hi
     * @return
     */
    private int partition(int[] nums,int lo,int hi){
        //将lo作为哨兵,将哨兵放到合法的位置上
        int pivot = nums[lo];
        //将[lo+1,hi]进行位置的交换
        int i = lo+1,j = hi;
        while(i <= j){
            while(i<=hi && nums[i] < pivot){
                i++;
            }
            while (j> lo && nums[j] >= pivot){
                j--;
            }
            if(i>=j){
                break;
            }
            swap(nums,i,j);
        }
        swap(nums,lo,j);
        return j;
    }

    private void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
